function Node(val, children) {
  this.val = val;
  this.children = children;
};


/**
 * @param {Node|null} root
 * @return {number[]}
 */
var preorder = function (root) {
  let result = [];
  if (root == null)
    return result;
  // 递归
  // function preorderNum(node) {
  //   for(let i = 0; i < node.children.length; i++) {
  //     preorderNum(node.children[i]);
  //   }
  //   result.push(node.val);
  // }
  // preorderNum(root);
  // 迭代
  let stack = [root];
  while (stack.length) {
    let node = stack[stack.length - 1];
    result.push(node.val);
    stack.splice(stack.length - 1, 1);
    for (let i = 0; i < node.children.length; i++) {
      stack.push(node.children[i]);
    }
  }
  return result.reverse();
};
